//
// Created by denglibin on 2020/6/13.
//
// 二叉树

#include <stdio.h>
#include <stdlib.h>

/**
 * 节点-结构
 */
typedef struct node
{
    int data;                       // 数据
    struct node *l_child, *r_child; // 左右子节点
} Node;

/**
 * 创建二叉树 按层次 从上到下 从左到右
 * @param nodes 节点指针数组
 * @param nodes_len 数组长度
 * @param node_create_num 节点已创建个数
 * @param arr 数据
 * @param arr_len 数组长度
 * @param start_index 从数组中取数据的位置
 */
static void createBinaryTree(Node *nodes[], int nodes_len, const int arr[], int arr_len, int index)
{
    if (index >= arr_len)
    {
        return;
    }
    for (int i = 0; i < nodes_len; i++)
    {
        nodes[i]->data = arr[index++];
        if (index >= arr_len)
        {
            return; // 遍历完成
        }
    }

    // 下一层 的节点 数组 长度
    int next_len = 2 * nodes_len; // 默认是上一层的2倍
    if (next_len > arr_len - index)
    {                               // 数组中剩余待遍历的数据比 上一层的2倍小
        next_len = arr_len - index; // 更正长度为 数组中剩余数据的大小
    }
    // 下一层的节点 数组
    Node **nextNodes = (Node **)calloc(next_len, sizeof(Node *));
    for (int i = 0, j = 0; i < nodes_len && j < next_len; i++)
    {
        Node *left = (Node *)calloc(1, sizeof(Node));
        nodes[i]->l_child = left;
        nextNodes[j++] = left;
        if (j >= next_len)
        {
            break;
        }
        Node *right = (Node *)calloc(1, sizeof(Node));
        nodes[i]->r_child = right;
        nextNodes[j++] = right;
    }
    // 创建下一层
    createBinaryTree(nextNodes, next_len, arr, arr_len, index);
    free(nextNodes); // 释放数组空间
}

/**
 * 先序遍历
 * @param root
 */
static void preOrderTraverse(Node *root, int deep)
{
    if (root)
    {
        for (int i = 0; i < deep; i++)
        {
            printf("- ");
        }
        printf("%d\n", root->data);
        preOrderTraverse(root->l_child, deep + 1); // 左 子树
        preOrderTraverse(root->r_child, deep + 1); // 右 子树
    }
}
/**
 * 中序遍历
 * @param root
 * @param deep
 */
static void inOrderTraverse(Node *root, int deep)
{
    if (root)
    {
        for (int i = 0; i < deep; i++)
        {
            printf("- ");
        }
        preOrderTraverse(root->l_child, deep + 1); // 左 子树
        printf("%d\n", root->data);
        preOrderTraverse(root->r_child, deep + 1); // 右 子树
    }
}
/**
 * 后序遍历
 * @param root
 * @param deep
 */
static void posOrderTraverse(Node *root, int deep)
{
    if (root)
    {
        for (int i = 0; i < deep; i++)
        {
            printf("- ");
        }
        preOrderTraverse(root->l_child, deep + 1); // 左 子树
        preOrderTraverse(root->r_child, deep + 1); // 右 子树
        printf("%d\n", root->data);
    }
}

/**
 * 获取树的深度
 * @param root 根节点
 * @param currentDeep 当前遍历的深度
 * @param deep 最终深度的传出参数
 */
static void getDeep(Node *root, int currentDeep, int *deep)
{
    if (!root)
    {
        return;
    }
    if (currentDeep > *deep)
    {
        *deep = currentDeep;
    }
    getDeep(root->l_child, currentDeep + 1, deep);
    getDeep(root->r_child, currentDeep + 1, deep);
}
/**
 * 获取二叉树的深度
 * @param node
 * @return
 */
static int depth(Node *node)
{
    if (node == NULL)
    {
        return 0;
    }
    int depth = 1;
    getDeep(node, 1, &depth);
    return depth;
}

int main27(int argc, char *argv[])
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    Node node;
    Node *nodes[1] = {&node};
    createBinaryTree(nodes, 1, arr, sizeof(arr) / sizeof(int), 0);
    // preOrderTraverse(&node, 0);
    // inOrderTraverse(&node, 0);
    // posOrderTraverse(&node, 0);
    int deep;
    getDeep(&node, 1, &deep);
    printf("deep: %d\n", deep);
    return 0;
}
